package complexdatastructure.unionfindset;

/**
 * @Classname : RedundantConnection
 * @Description :
 * <a href="https://leetcode.cn/problems/redundant-connection/">684. 冗余连接</a>
 * <a href="https://oi-wiki.org/ds/dsu/">并查集</a>
 * @Author : chentianyu
 * @Date 2023/2/8 22:25
 */


public class RedundantConnection {
    public int[] findRedundantConnection(int[][] edges) {
        int[] ans = null;
        UF uf = new UF(edges.length + 1);
        for (int[] edge : edges) {
            if (!uf.union(edge[0], edge[1])) ans = edge;
        }
        return ans;
    }

    public class UF {
        private int[] parent;  // 记录节点的父节点
        private int[] rank;  // 记录集合的层级

        public UF(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;  // 初始化每个节点的父节点是自己
                rank[i] = 1;  // 开始每个节点都是一个集合，层级为1
            }
        }

        /**
         * 查找节点的根节点
         */
        public int find(int x) {
            // 路径压缩：查找时将当前节点父节点修改为集合根节点，从而加速下次查找
            return (x == parent[x]) ? x : (parent[x] = find(parent[x]));
        }

        /**
         * 合并两个节点对应的集合
         * 若两个节点已经在一个集合则返回 false
         */
        public boolean union(int x, int y) {
            x = find(x);
            y = find(y);
            // 若两个节点已经在一个集合则返回 false
            if (x == y) return false;
            // 合并两个节点对应的集合，将层级小的集合合并到层级大的集合
            if (rank[x] >= rank[y]) {
                if (rank[x] == rank[y]) rank[x]++;
                parent[y] = x;
            } else {
                parent[x] = y;
            }
            return true;
        }
    }
}
